//
//  Problem1409.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/4.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1409. 查询带键的排列
 给你一个待查数组 queries ，数组中的元素为 1 到 m 之间的正整数。 请你根据以下规则处理所有待查项 queries[i]（从 i=0 到 i=queries.length-1）：

 一开始，排列 P=[1,2,3,...,m]。
 对于当前的 i ，请你找出待查项 queries[i] 在排列 P 中的位置（下标从 0 开始），然后将其从原位置移动到排列 P 的起始位置（即下标为 0 处）。注意， queries[i] 在 P 中的位置就是 queries[i] 的查询结果。
 请你以数组形式返回待查数组  queries 的查询结果。

 示例 1：
     输入：queries = [3,1,2,1], m = 5
     输出：[2,1,2,1]
     解释：待查数组 queries 处理如下：
     对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，接着我们把 3 移动到 P 的起始位置，得到 P=[3,1,2,4,5] 。
     对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,3,2,4,5] 。
     对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，接着我们把 2 移动到 P 的起始位置，得到 P=[2,1,3,4,5] 。
     对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,2,3,4,5] 。
    因此，返回的结果数组为 [2,1,2,1] 。
 示例 2：
     输入：queries = [4,1,2,2], m = 4
     输出：[3,1,2,0]
 示例 3：
     输入：queries = [7,5,5,8,3], m = 8
     输出：[6,5,0,7,5]
 提示：
     1 <= m <= 10^3
     1 <= queries.length <= m
     1 <= queries[i] <= m
 */
@objcMembers class Problem1409: NSObject {
    func solution() {
        print(processQueriesBIT([3,1,2,1], 5))
        print(processQueries([4,1,2,2], 4))
        print(processQueries([7,5,5,8,3], 8))
        print(processQueries([8,7,4,2,8,1,7,7], 8))
    }
    
    /*
     1: 创建一个长度为m的数组list，并赋值从100递增，例如
     [100, 101, 102, 103, 104, 105]
     2: 设置一个最小值min=99
     3: 遍历数组queries：[5, 2, 4, 5]， 例如第一个数：i=5 在上面的列表是：n=104, n在队列中的位置是：list[i-1] - min - 1
     4: 让数组list中 > 104的数都-1， 然后让list[i-1] = min

     
     */
    func processQueries(_ queries: [Int], _ m: Int) -> [Int] {
        var list:[Int] = Array(repeating: 100, count: m)
        for i in 0..<m {
            list[i] = i + 100
        }
        
        var result: [Int] = Array(repeating: 0, count: queries.count)
        var min = 99
        for (n, i) in queries.enumerated() {
            result[n] = list[i-1] - min - 1
            
            for j in 0..<list.count {
                if  list[j] > list[i-1] {
                    list[j] -= 1
                }
            }
            list[i-1] = min
            min -= 1
            
        }
        
        return result
    }
    
    /*
     树状数组：
     1: 创建一个数组：pos[m+n]
     2:
     */
    func processQueriesBIT(_ queries: [Int], _ m: Int) -> [Int] {
        // 创建一个pos数据，存储所有节点的位置，从n开始
        var pos:[Int] = Array(repeating: 0, count: m)
        for i in 0..<m {
            pos[i] = queries.count + i + 1
        }
        
        // 创建一个树状数组
        let bTree = BIT(n: m+queries.count)
        // 更新数组
        for i in 0..<m {
            bTree.update(queries.count+i, 1)
        }


        // 存放结果集
        var list:[Int] = Array(repeating: 0, count: queries.count)
        
        for (i, value) in queries.enumerated() {
            // 1: 将value在bTree对应的位置 取出后：让他-1
            let n = pos[value - 1]
            bTree.update(n-1, -1)
            // 2: 计算value在bTree对应的位置的前缀和
            list[i] = bTree.query(n)
            // 3: 更新value在pos的位置信息
            pos[value-1] = queries.count - i
            // 4: 将新的值插入到bTree中
            bTree.update(pos[value-1]-1, 1)
        }
        
        return list
    }
    
    class BIT {
        var list: [Int] = []
        
        init(n: Int) {
            list = Array(repeating: 0, count: n+1)
        }
        
        // 用于：计算下一个位置的索引
        func lowbit(_ i: Int) -> Int {
            return i & -i
        }
        
        // 更改这个值
        func update(_ i: Int, _ value: Int) {
            var nI = i+1
            while nI < list.count {
                list[nI] += value
                nI += lowbit(nI)
            }
        }
        
        // 查询这个值
        func query(_ i: Int) -> Int {
            var sum: Int = 0
            var nI : Int = i
            while nI != 0 {
                sum += list[nI]
                nI -= lowbit(nI)
            }
            return sum
        }
    }
}


